#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

/********************** 定义与初始化 ***********************************/
struct node {
    int key;
    int val;
    struct node *prev;
    struct node *next;  
};

struct doublelink {
    struct node *head;
    struct node *tail;
};

#define LOAD_FACTOR 0.7
enum {
    NOEXIST,    //不存在
    DELETED,    //已删除
    EXISTED         
};
struct hashnode {
    int state;      //状态
    struct node *map;   //映射
};
struct hashtable {
    int tsize;      //哈希表大小   
    struct hashnode **table;      
};

typedef struct {
    int capacity;   //cache容量
    int count;      //当前大小
    struct doublelink *dll; //双向链表，最新的节点在头，最少用的节点在尾
    struct hashtable *ht; //数组式哈希，保存节点映射
} LRUCache;

void doublelink_init(struct doublelink **dll) {
    (*dll)->head = malloc(sizeof(struct node));
    assert((*dll)->head);
    (*dll)->tail = malloc(sizeof(struct node));
    assert((*dll)->tail);

    (*dll)->head->next = (*dll)->tail; (*dll)->head->prev = NULL;
    (*dll)->tail->prev = (*dll)->head; (*dll)->tail->next = NULL;
}
void hashtable_init(struct hashtable **ht, int tsize) {
    int i;
    (*ht)->tsize = tsize;
    (*ht)->table = malloc(sizeof(struct hashnode *) * tsize);
    assert((*ht)->table);

    for (i = 0; i < tsize; i++) {
        (*ht)->table[i] = malloc(sizeof(struct hashnode));
        assert((*ht)->table[i]);

        (*ht)->table[i]->state = NOEXIST;
        (*ht)->table[i]->map = NULL;
    }
}

LRUCache* lRUCacheCreate(int capacity) {
    int i;
    LRUCache* cache = malloc(sizeof(*cache));
    cache->capacity = capacity;
    cache->count = 0;

    cache->dll = malloc(sizeof(struct doublelink));
    assert(cache->dll);
    cache->ht = malloc(sizeof(struct hashtable));
    assert(cache->ht);

    doublelink_init(&cache->dll);
    //如果装载因子太大，会导致性能直线下降，运行超时！！！
    hashtable_init(&cache->ht, cache->capacity/LOAD_FACTOR);
    return cache;
}


/********************** 哈希表操作 ***********************************/
int myhash(struct hashtable *ht, int key) {
    return (key%ht->tsize);
}

// 查找key是否存在，没有找到，或已经被删除时返回-1
int search_hashtable(struct hashtable *ht, int key) {
    int detect_cnt = 0, index = myhash(ht, key);
    while (ht->table[index]->state != NOEXIST) {
        if (ht->table[index]->state == DELETED) return -1;
        else if (ht->table[index]->map->key == key) return index;
        else {
			//可能一直找不到目标
			if (detect_cnt >= ht->tsize) return -1;
			detect_cnt++;
			index = (++index) % ht->tsize;  //线性探测
		}    
    }
    return -1;  //不存在
}
int addmap_hashtable(struct hashtable *ht, struct node *node)
{   
    int index;
    //找空位
    index = myhash(ht, node->key);
    while (ht->table[index]->state == EXISTED) {  
        index = (++index) % ht->tsize;
    }

    ht->table[index]->state = EXISTED;
    ht->table[index]->map = node;
    return 1;
}
int delmap_hashtable(struct hashtable *ht, int key)
{   
    int index;
    index = search_hashtable(ht, key);
    if (index < 0) //不存在，退出
        return 0;

    ht->table[index]->state = DELETED;
    ht->table[index]->map = NULL;
    return 1;
}

/********************** 双向链表操作 ***********************************/
void insert_head_dll(struct doublelink *dll, struct node *node)
{
    struct node *save = dll->head->next;
    dll->head->next = node; node->next = save;
    node->prev = dll->head; save->prev = node;
}
//目标节点从双向链表中脱离，要事先保存好目标节点
void drop_node_dll(struct node *node)
{
    node->prev->next = node->next;
    node->next->prev = node->prev;
}

/********************** LRU操作 ***********************************/
int lRUCacheGet(LRUCache* obj, int key) {
    //在哈希表中查找，
    struct node *temp;
    int index = search_hashtable(obj->ht, key);
    if (index < 0) return -1;
    else {
        temp = obj->ht->table[index]->map;
        drop_node_dll(obj->ht->table[index]->map);
        insert_head_dll(obj->dll, temp);
        return temp->val;  
    }
}

void lRUCachePut(LRUCache* obj, int key, int value) {
    struct node *newnode, *temp;
    int index;
    index = search_hashtable(obj->ht, key);
    if (index >= 0) {    //如果key存在，更新节点值，且将节点的位置调整到链表头
        temp = obj->ht->table[index]->map;
		temp->val = value;  
		//是头节点
		if (temp == obj->dll->head->next) 
            return ;

        drop_node_dll(obj->ht->table[index]->map);
        insert_head_dll(obj->dll, temp);
    }
    else {  //如果不存在，则插入
        newnode = malloc(sizeof(struct node));
        newnode->val = value;
        newnode->key = key;

        if (obj->count >= obj->capacity) {    //如果缓存已满，取消尾节点在哈希表中的映射，释放内存
            temp = obj->dll->tail->prev;
            drop_node_dll(obj->dll->tail->prev);
            delmap_hashtable(obj->ht, temp->key);   
            free(temp); temp = NULL;
            obj->count--;
        }
        //插入新节点
        addmap_hashtable(obj->ht, newnode);
        insert_head_dll(obj->dll, newnode);
        obj->count++;
    }
}


void lRUCacheFree(LRUCache* obj) {
    int i;
    free(obj->dll->head);
    free(obj->dll->tail);
    free(obj->dll);
    for (i = 0; i < obj->ht->tsize; i++) 
        if (obj->ht->table[i]->state == EXISTED) 
            free(obj->ht->table[i]->map);
    free(obj->ht);
}

void display_dll(struct doublelink *dll)
{
	struct node *p = dll->head->next;
	while (p != dll->tail) {
		printf("%d-%d ",p->key,p->val);
		p = p->next;
	}
}
void main()
{

	LRUCache* cache = lRUCacheCreate(2);
	//未溢出时插入没有问题
	lRUCachePut(cache, 2, 1);
	lRUCachePut(cache, 2, 2);
	
	//取缓存没有问题
	// lRUCacheGet(cache, 1);

	// 将已存在结节调整位置没有问题
	// lRUCachePut(cache, 1, 1);

	//调整指针没有问题
	// struct node *temp = cache->dll->tail->prev;
	// get_node_dll(cache->dll, cache->dll->tail->prev);
	// insert_head_dll(cache->dll, temp);

	// lRUCachePut(cache, 3, 3);
	display_dll(cache->dll);
}
/**
 * Your LRUCache struct will be instantiated and called as such:
 * LRUCache* obj = lRUCacheCreate(capacity);
 * int param_1 = lRUCacheGet(obj, key);
 
 * lRUCachePut(obj, key, value);
 
 * lRUCacheFree(obj);
*/